#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创建日期：2020年10月20日
描    述：
'''


class Solution(object):
    def numSubarraysWithSum(self, A, S):
        """
        :type A: List[int]
        :type S: int
        :rtype: int
        """
        size = len(A)
        dp = [0 for _ in range(size + 1)]
        for i in range(0, size):
            dp[i + 1] = dp[i] + A[i]

        res = 0
        dpkey = {}
        for p in dp:
            res += dpkey.get(p, 0)
            dpkey[p + S] = dpkey.get(p + S, 0) + 1

        return res
